#ifndef __QUICK_SORT_H__
#define __QUICK_SORT_H__

// Elements in the array include the elem at location 
// start, but not end
template<class Type>
void quickSortRecur(Type *array, int start, int end) {
    // No more than one elem to be sorted, no need to sort
    if (start >= end - 1) {
        return;
    }

    int pivot = (start + end) / 2;
    Type pivot_val = array[pivot];
    array[pivot] = array[start];

    int loc = start;
    int l = start + 1;
    int r = end;
    Type val;

    while (l < r) {
        if (array[l] < pivot_val) {
            array[loc] = array[l];
            l++;
            loc++;
        }
        else {
            val = array[l];
            array[l] = array[r-1];
            array[r-1] = val;
            r--;
        }
    }

    array[loc] = pivot_val;

    quickSortRecur(array, start, loc);
    quickSortRecur(array, loc + 1, end);
}

template<class Type>
void quickSort(Type *array, int n) {
    quickSortRecur(array, 0, n);    
}

#endif

